package com.rui.study.algorithm.P_动态规划_最长递增子序列;

import java.util.Arrays;
import java.util.Random;

public class Solution3动态规划_状态转移表 {

    public static int maxLength(int[] a) {
        int n = a.length;
        int[] maxLen = new int[n];

        for (int i = 0; i < n; i++) {
            maxLen[i] = 1;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (a[i] >= a[j]) {
                    if (maxLen[j] > maxLen[i] - 1)
                        maxLen[i] = maxLen[j] + 1;
                }
            }
        }

        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            if (maxLen[i] > max) max = maxLen[i];
        }
        System.out.println(Arrays.toString(maxLen));

        return max;
    }

    public static void main(String[] args) {
        int n = 5000;
        int[] a = new int[n];
        Random r = new Random(31);
        for (int i = 0; i < n; i++) {
            a[i] = r.nextInt(n);
        }
        System.out.println(Arrays.toString(a));
        long start = System.currentTimeMillis();
        int maxLen = Solution3动态规划_状态转移表.maxLength(a);
        long end = System.currentTimeMillis();
        System.out.println("最长递增子序列长度：" + maxLen + ", 耗时：[" + (end - start) + "ms]---动态规划_状态转移表");
    }
}
